home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / language / embedded / simulato / v2_3_mc6.tz / v2_3_mc6 / testfiles / treefnd4.asm < prev    next >
Assembly Source File  |  1994-05-02  |  17KB  |  384 lines
  1. ***************************************************************************
  2. *
  3. *       ASSIGNMENT:  PROG3
  4. *       DUE DATE:    NOVEMBER 16, 1992
  5. *       DESCRIPTION: This program stores data in a binary tree structure.
  6. *                       The data to be stored are the integers 0-9.  The 
  7. *                       subroutine MALLOC will be used to create the 
  8. *                       neccessary nodes at run time.  Each node will 
  9. *                       consist of the left pointer address (4 bytes) the
  10. *                       word-sized integer (2 bytes) and the right pointer
  11. *                       address (4 bytes).  The program will allow a user
  12. *                       to enter commands from the keyboard as follows:
  13. *                               1. I x -- Will insert the integer x into
  14. *                                         the tree.
  15. *                               2. S x -- Will search the tree for x.
  16. *                               3. P   -- Will print the tree in presearch
  17. *                                         format.
  18. *                               4. E   -- Ends the program.
  19. ***************************************************************************
  20.  
  21. **** MAIN ROUTINE ****
  22. * Functions as a place for processing commands and calling
  23. * seperate modules to both insert search and print the tree.
  24. **********************
  25. **** RESOURCE ALLOCATION ****
  26. * D2 -> holds user command and parameter after command process.
  27. * A2 -> generic pointer to be used by any.
  28. *****************************
  29.  
  30.         ORG $1000
  31. INIT_TREE CLR.L $5000                   ;set up null node in tree to
  32.         MOVE.W #-1,$5004                ;trap operations before first
  33.         CLR.L $5006                     ;insert.
  34.  
  35. START   JSR WriteEOL                    ;make spaces so
  36.         JSR WriteEOL                    ;it's easier to read
  37.         LEA COMMANDMSG,A0               ;Load in prompt.
  38.         JSR WriteString                 ;Write string to screen.
  39.         LEA COMMAND,A0                  ;load in place to store command
  40.         MOVE.L A0,-(A7)                 ;save this locator on stack.
  41.         JSR ReadString                  ;and then read in the string.
  42.         MOVEA.L (A7)+,A0                ;Restore pointer to command string.
  43.         CLR.L D2                        ;Clear d2, to be used as command.
  44.         JSR READCOMMAND                 ;Parse command string.
  45.         MOVE.B (A0)+,D2                 ;Load in read command character.
  46.  
  47. CASE_E  CMPI.B #'E',D2                  ;Compare command to exit code.
  48.         BNE.S CASE_I                    ;if not exit compare to nxt. case.
  49.         BRA.W END_IT                    ;else quit program.
  50.  
  51. CASE_I  CMPI.B #'I',D2                  ;Compare to insert command code.
  52.         BNE.S CASE_S                    ;if not look @ nxt. case.
  53.         MOVE.B (A0),D2                  ;Load in parameter value from str.
  54.         JSR PUTNTREE                    ;Jump to place paramter into tree.
  55.         BRA.S START                     ;Return to nxt. commmand.
  56.  
  57. CASE_S  CMPI.B #'S',D2                  ;Compare to search for param. in
  58.         BNE.S CASE_P                    ;if not look @ nxt. case.
  59.         MOVE.B (A0),D2                  ;load param. value from string.
  60.         JSR SEARCH                      ;search for parameter in string.
  61.         TST.W D1                        ;test found integer flag.
  62.         BEQ.S S_NOFIND                  ;if zero. integer was not found
  63.         LEA INTEGERMSG,A0               ;place ptr. to found message.
  64.         JSR WriteString                 ;and write to the screen.
  65.         MOVE.B D2,D0                    ;place low byte into d0 for print.
  66.         JSR WriteChar                   ;Print integer out.
  67.         LEA S_FOUNDMSG,A0               ;Load in tail of message.
  68.         JSR WriteString                 ;and print out.
  69.         BRA.W START                     ;return for nxt. command.
  70. S_NOFIND LEA INTEGERMSG,A0              ;else place ptr. to not found msg.
  71.         JSR WriteString                 ;and write to screen.
  72.         MOVE.B D2,D0                    ;place low byte into d0 for print.
  73.         JSR WriteChar                   ;print parameter
  74.         LEA S_NOFINDMSG,A0              ;Load in tail of message.
  75.         JSR WriteString                 ;and print message.
  76.         BRA.W START                     ;return for nxt. command.
  77.  
  78. CASE_P  CMPI.B #'P',D2                  ;Compare for parameter to print
  79.         BNE.W BAD_COMMAND               ;if not get new command.
  80.         JSR PRINTREE                    ;Print tree.
  81.         BRA.W START                     ;return for nxt. command.
  82.  
  83. BAD_COMMAND LEA BAD_MSG,A0              ;Load bad command message.
  84.         JSR WriteString                 ;Write the message.
  85.         BRA.W START                     ;Get next command.
  86.  
  87. END_IT  MOVE #228,D7                    ;Quit program.
  88.         TRAP #14
  89.  
  90.         NOLIST                          ;Include available subroutines.
  91.         DC.W 0
  92.         INCLUDE "samples.asm"
  93.         LIST
  94.  
  95.  
  96. **** SUBROUTINE READCOMMAND ****
  97. * This subroutine places the 20 character command string into the standard
  98. * format of <ONE_LETTER_COMMAND><ONE_DIGIT_DECIMAL_NUMBER>. Where
  99. * ONE_LETTER_COMMAND = {I,S,P,E},and ONE_DIGIT_NUMBER ={0,1,2,3,4,5,6,7,8,9}
  100. * The parsed string will remain at the global location marked by the label
  101. * COMMAND.
  102. ********************************
  103. **** RESOURCE ALLOCATION ****
  104. * A0 -> points to beginning of command string must be restored.
  105. * A2 -> temporary position pointer.
  106. *****************************
  107. **** SUBROUTINES ****
  108. * CALLS:    ----
  109. * CALL BY:  MAIN
  110. *********************
  111. READCOMMAND MOVEA.L A0,A2           ;Load in position ptr.
  112.             MOVE.W #0,FOUND_DIGIT   ;clear multiple digit flag.
  113. NEXTPLACE   MOVE.B (A0)+,D2         ;Load in next character.
  114.             TST.B D2                ;Test for end of string.
  115.             BEQ.W END_RCOMMAND      ;if end go to end.
  116.             CMPI.B #'i',D2          ;Look for lower case insert command
  117.             BEQ.W SET_I             ;if equal set up command string for in.
  118.             CMPI.B #'I',D2          ;or if equal to upper case do same.
  119.             BEQ.W SET_I             ;by branching to same routine.
  120.             CMPI.B #'s',D2          ;Repeat case finding for s or S
  121.             BEQ.W SET_S             ;by performin the same comparisons.
  122.             CMPI.B #'S',D2          ;The test needs to look @ a possible
  123.             BEQ.W SET_S             ;8 test cases.
  124.             CMPI.B #'p',D2          ;Single operand commands will not be
  125.             BEQ.W SET_P             ;distinguished.
  126.             CMPI.B #'P',D2          ;The routine will end regardless of
  127.             BEQ.W SET_P             ;whether it finds a second operand
  128.             CMPI.B #'e',D2          ;or not when it hits the null charachter.
  129.             BEQ.W SET_E             ;Set up to find specific letters because
  130.             CMPI.B #'E',D2          ;of the need to convert.
  131.             BEQ.W SET_E             ;Numbers do not need to be converted
  132.             CMPI.B #'0',D2          ;because there is only one case.
  133.             BLT.S NEXTPLACE         ;Therefore they will be tested in
  134.             CMPI.B #'9',D2          ;a range from 0-9.
  135.             BGT.S NEXTPLACE         ;NO ERROR!!!!!!! WILL BE GIVEN FOR
  136. SET_NUM     MOVE.B D2,(A2)          ;The first number found ends the command.
  137.             CMPI.W #1,FOUND_DIGIT   ;Look to see if there is already a digit.
  138.             BEQ.S TOO_MANY_D        ;if so end routine. else
  139.             MOVE.W #1,FOUND_DIGIT   ;store a digit has already been entered
  140.             BRA.W NEXTPLACE         ;and look for end of string.
  141.  
  142. TOO_MANY_D  LEA MANY_DMSG,A0        ;Load ptr. for message.
  143.             JSR WriteString         ;Print.
  144.             LEA COMMAND,A0          ;retore command ptr. to corrupt.
  145.             MOVE.B #'Z',(A0)        ;corrupt command message.
  146.  
  147. END_RCOMMAND LEA COMMAND,A0         ;Restore the command string ptr.
  148.             CMPI.W #1,FOUND_DIGIT   ;Make sure that a digit was input
  149.             BEQ.S GOOD_COMMAND      ;if so end normal
  150.             LEA NO_DMSG,A0          ;else print out 
  151.             JSR WriteString         ;no digits found message.
  152.             LEA COMMAND,A0          ;restore the command string ptr.
  153.             MOVE.B #'Z',(A0)        ;and corrupt command message.
  154.  
  155. GOOD_COMMAND ADDQ.L #1,A2           ;Point to next command.
  156.             MOVE.B #17,D2           ;Load the number of potential null char.
  157. REPEAT_0    MOVE.B #0,(A2)+         ;zero byte increment pointer.
  158.             DBRA D2,REPEAT_0        ;repeat till end.
  159.             RTS
  160.  
  161. SET_I       MOVE.B #'I',(A2)+
  162.             BRA.W NEXTPLACE
  163. SET_E       MOVE.B #'E',(A2)+
  164.             MOVE.W #1,FOUND_DIGIT
  165.             BRA.W NEXTPLACE
  166. SET_S       MOVE.B #'S',(A2)+
  167.             BRA.W NEXTPLACE
  168. SET_P       MOVE.B #'P',(A2)+
  169.             MOVE.W #1,FOUND_DIGIT
  170.             BRA.W NEXTPLACE
  171.  
  172.  
  173.  
  174.  
  175. **** SUBROUTINE SEARCH ****
  176. * This subroutine will search the tree starting from the root
  177. * node @ address: $5000. The parameter it is to search must be of
  178. * word length in d2.  The subroutine will return in d1 a true flag
  179. * if the param was found or a false flag if the param was not.
  180. * The paramter will return where the said paramter should have been,
  181. * left or right, in d3--a 0 corresponds to left, a 1 to right.  The
  182. * subroutine will return in a2 a pointer to the last node searched.
  183. ****************************
  184. **** RESORCE ALLOCATION ****
  185. * A2 -> pointer to next tested node.
  186. * D2 -> the integer being searched for.
  187. * D3 -> right/left flag
  188. * D1 -> found flag.
  189. ****************************
  190. **** SUBROUTINES ****
  191. * CALLS:   ----
  192. * CALL BY:  PUTNTREE
  193. *           MAIN
  194. *********************
  195. SEARCH  MOVEA.L #$5000,A2       ;Load in top of tree.
  196.  
  197. CURRENT CMP.W 4(A2),D2          ;Look @ current node.
  198.         BGT.S GO_RIGHT          ;If param is > node look to see if right.
  199.         BLT.S GO_LEFT           ;If param is < node look to see if left.
  200.  
  201. ITS_EQ  MOVE.W #1,D1            ;Set flag to true.
  202.         BRA.S END_SEARCH        ;and quit search.
  203.  
  204. GO_RIGHT MOVE.W #1,D3           ;Move in looked @ right ptr.
  205.         TST.L 6(A2)             ;Look @ right ptr. of current node.
  206.         BEQ.S SEARCH_NOFIND     ;if zero. end routine w/o finding.
  207.         MOVEA.L 6(A2),A2        ;Load right ptr. into current ptr.
  208.         BRA.S CURRENT           ;Look @ new node.
  209.  
  210. GO_LEFT CLR.W D3                ;Move in looked @ left ptr. flag.
  211.         TST.L (A2)              ;Look @ left ptr. of current node.
  212.         BEQ.S SEARCH_NOFIND     ;if zero. end routine w/o finding.
  213.         MOVEA.L (A2),A2         ;else load left ptr. into current ptr.
  214.         BRA.S CURRENT           ;Look @ new node.
  215.  
  216. SEARCH_NOFIND CLR.W D1          ;Set found flag to false.
  217. END_SEARCH RTS                  ;Return.
  218.  
  219. **** SUBROUTINE PUTNTREE ****
  220. * This subroutine uses the search subroutine to see if there is already
  221. * a node w/ the paramter value which is in d2.  If there is not it uses
  222. * the left/right flag, d3, to locate the postion where the new node 
  223. * should be inserted.  When a new node is neccessary the provided sub.
  224. * malloc is used to request 10 bytes of memory from the heap--4 bytes
  225. * for the left-pointer address, 2 bytes for the integer, and 4 bytes
  226. * for the right-pointer address.  The node pointed to by a2, the last
  227. * node looked @ by the search routine, has its left or right ptr. 
  228. * initialized based on the left/right flag to the ptr. of a0--returned
  229. * by malloc as the block requested.  The new node's pointers are both
  230. * set to zero and the integer given the param value.  Internal 
  231. * representation of integers is in ASCII.
  232. ******************************
  233. **** RESOURCE ALLOCATION ****
  234. * A0 -> pointer to new node, returned by malloc.
  235. * A2 -> pointer to last node detected by search.
  236. * D0 -> parameter for WriteChar, the character to be printed.
  237. * D2 -> user input of the integer being looked for and inserted.
  238. *****************************
  239. **** SUBROUTINES ****
  240. * CALLS:    malloc
  241. *           SEARCH
  242. * CALLED BY:MAIN
  243. *********************
  244. PUTNTREE MOVEA.L #$5000,A0      ;Load in top of tree.
  245.         CMPI.W #-1,4(A0)        ;Look @ root node to see if there
  246.         BEQ.S FIRST_INSERT      ;are any nodes, if not insert this as 1st.
  247.  
  248.         JSR SEARCH              ;else look for param. in tree.
  249.         TST.W D1                ;if param is found go to message.
  250.         BNE.S I_FOUNDIT         ;by testing flag for true.
  251.  
  252. R_OR_L  TST.W D3                ;test right/left flag for placement.
  253.         BEQ.S LEFT_INSERT       ;if zero left insert.
  254.         MOVE.L #10,D0           ;else for right insert Load block.
  255.         JSR malloc              ;and allocate memmory.
  256.         MOVE.L A0,6(A2)         ;initiallize right pointer of node to
  257.         CLR.L (A0)              ;new node, and clear pointers of new node.
  258.         CLR.L 6(A0)             ;--clear right ptr.--
  259.         MOVE.W D2,4(A0)         ;load integer.
  260.         BRA.S GOOD_IN           ;end routine.
  261.  
  262. LEFT_INSERT MOVE.L #10,D0       ;load size for new block.
  263.         JSR malloc              ;allocate memmory.
  264.         MOVE.L A0,(A2)          ;initiallize left pointer of old node.
  265.         CLR.L (A0)              ;clear pointers--left--
  266.         CLR.L 6(A0)             ;--right--
  267.         MOVE.W D2,4(A0)         ;load integer.
  268.         BRA.S GOOD_IN           ;end routine.
  269.  
  270. FIRST_INSERT MOVE.W D2,4(A0)    ;load integer--pointers previously init.
  271.         MOVE.L #10,D0           ;load size
  272.         JSR malloc              ;allocate memmory and end routine.
  273.  
  274. GOOD_IN LEA GOOD_INMSG,A0       ;Load successful insert mess.
  275.         JSR WriteString         ;Print out.
  276.         MOVE.B D2,D0            ;Load integer inserted.
  277.         JSR WriteChar           ;Print out.
  278.         BRA.S END_PUTNTREE      ;End routine.
  279.  
  280.  
  281. I_FOUNDIT LEA INTEGERMSG,A0     ;Load message to print error
  282.         JSR WriteString         ;write first word of message.
  283.         MOVE.B D2,D0            ;load to print out integer.
  284.         JSR WriteChar           ;Write intger.
  285.         LEA I_FOUNDMSG,A0       ;Load tail of message.
  286.         JSR WriteString         ;Write to screen.
  287.  
  288. END_PUTNTREE RTS                ;End routine.
  289.  
  290. **** SUBROUTINE PRINTREE ****
  291. * This subroutine prints the contents of the binary tree stored in the
  292. * heap @ location $5000.  The printing will use pre-order traversal.
  293. *****************************
  294. **** RESOURCE ALLOCATION ****
  295. * A2 -> generic pointer to nodes.
  296. * D0 -> parameter for WriteChar, the parameter to printed.
  297. *****************************
  298. **** SUBROUTINES ****
  299. * CALLS: WriteEOL
  300. *       WriteChar
  301. * CALLED BY:    MAIN
  302. *********************
  303. PRINTREE JSR WriteEOL           ;Print new line
  304.         MOVEA.L #$5000,A2       ;Load location of top of tree.
  305.         CMPI.W #-1,4(A2)        ;Look @ top node if flag exit.
  306.         BEQ.S END_PRINTREE      ;exit.
  307.  
  308.         MOVE.L #-1,-(A7)        ;Push end of print flag to stack.
  309.  
  310. P_LEFT  MOVE.W 4(A2),D0         ;Load integer of node.
  311.         JSR WriteChar           ;Print the integer out.
  312.         MOVE.W #' ',D0          ;Load in a space.
  313.         JSR WriteChar           ;Print a space.
  314.         TST.L 6(A2)             ;Test if right branch is valid.
  315.         BEQ.S P_NORIGHT         ;if not valid(0) do not push address
  316.         MOVE.L 6(A2),-(A7)      ;else push address of right to stack.
  317. P_NORIGHT TST.L (A2)            ;look @left 
  318.         BEQ.S NO_LEFT           ;if left ptr. is not valid go no_left.
  319.         MOVEA.L (A2),A2         ;else load in left ptr. to new node.
  320.         BRA.S P_LEFT            ;stay in left print loop.
  321.  
  322. NO_LEFT MOVE.L (A7)+,A2         ;load in last valid right node.
  323.         CMPA.L #-1,A2           ;compare address to end of print flag.
  324.         BEQ.S END_PRINTREE      ;if eopf then end pritree.
  325.         BRA.S P_LEFT            ;else use right node as current node.
  326.  
  327. END_PRINTREE RTS                ;return from sub.
  328.  
  329.  
  330. *******************
  331. **** VARIABLES ****
  332. *******************
  333.         CNOP 0,2
  334. INTEGERMSG DC.B 13,10,'Integer ',0
  335.         CNOP 0,2
  336. S_FOUNDMSG DC.B ' was found in search tree.',13,10,0
  337.         CNOP 0,2
  338. S_NOFINDMSG DC.B ' was not found.',13,10,0
  339.         CNOP 0,2
  340. COMMANDMSG DC.B 'Please enter command: ',0
  341.         CNOP 0,2
  342. I_FOUNDMSG DC.B ' already exists in tree.',13,10,0
  343.         CNOP 0,2
  344. MANY_DMSG DC.B 13,10,'Integer too large, 0-9 only!!!',13,10
  345.           DC.B 'or Command does not accept an integer.',13,10,0
  346.         CNOP 0,2
  347. BAD_MSG DC.B 13,10,'INVALID COMMAND!!!-Please try again.',0
  348.         CNOP 0,2
  349. GOOD_INMSG DC.B 13,10,'Successfull insertion of ',0
  350.         CNOP 0,2
  351. NO_DMSG DC.B 13,10,'No Digits were found.',13,10,0
  352.         CNOP 0,2
  353. FOUND_DIGIT DC.W 0
  354. COMMAND DC.B 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
  355.         END
  356.  
  357.  
  358.  
  359.  
  360.  
  361.  
  362.  
  363.  
  364.  
  365.  
  366.  
  367.  
  368.  
  369.         
  370.  
  371.  
  372.  
  373.  
  374.  
  375.  
  376.  
  377.  
  378.  
  379.  
  380.  
  381.  
  382.  
  383.  
  384.